package com.aigis.big4.tmp.javase;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Magic {
    static int N = 0;
    static int M = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("a 个数：");
        int n = sc.nextInt();
        System.out.println("b 个数：");
        int m = sc.nextInt();
        N = n;
        M = m;
        HashSet<Integer> setA = new HashSet<>();
        ArrayList<Integer> listB = new ArrayList<>();
        double sumA = 0;
        double sumB = 0;
        int a = 0;
        System.out.println("输入a元素：");
        for (int i = 0; i < n; i++) {
            a = sc.nextInt();
            setA.add(a);
            sumA += a;
        }
        System.out.println("输入b元素：");
        for (int i = 0; i < m; i++) {
            a = sc.nextInt();
            listB.add(a);
            sumB += a;
        }
        double aveA = sumA / n;
        double aveB = sumB / m;
        System.out.println("开始magic");
        magic(sumA, sumB, aveA, aveB, setA, listB);
        System.out.println(count);

    }

    static int count = 0;

    public static void magic(double sumA, double sumB, double aveA, double aveB, HashSet<Integer> setA,
                           ArrayList<Integer> listB) {
        if (listB.size() == 0) {
            return;
        }
        int n = setA.size();
        int m = listB.size();
        for (int i = 0; i < listB.size(); i++) {
            int value = listB.get(i);
            if ((sumA + value) / (n + 1) > aveA ) {//满足要求
                count ++;
                setA.add(value);
                listB.remove(i);
                aveA = (sumA + value) / (n + 1);
                aveB = (sumB - value) / (m - 1);
                dfs(sumA + value, sumB - value, aveA, aveB, setA, listB);//操作后，递归
            }
        }
    }

    public static void dfs(double sumA, double sumB, double aveA, double aveB, HashSet<Integer> setA,
                           ArrayList<Integer> listB) {
        if (listB.size() == 0) {
            count = listB.size() - 1;
            return;
        }
        int n = setA.size();
        int m = listB.size();
        for (int i = 0; i < listB.size(); i++) {
            int value = listB.get(i);
            if ((sumA + value) / (n + 1) > aveA && (sumB - value) / (m - 1) > aveB) {//满足要求
                setA.add(value);
                listB.remove(i);
                aveA = (sumA + value) / (n + 1);
                aveB = (sumB - value) / (m - 1);
                dfs(sumA + value, sumB - value, aveA, aveB, setA, listB);//操作后，递归
                listB.add(i, value);//未操作
                if (setA.size() == n + 1) {
                    setA.remove(value);
                }
                aveA = sumA / n;
                aveB = sumB / m;
            }
        }
    }
}
